package lec13dp2;

public class A {
    public static void main(String[] args) {
        int[] a = new int[]{
                1, 7, 3, 5, 9, 4, 8
        };
        int n = a.length;
        int[] dp = new int[n];//dp[x]  以a[x]为结尾的最长单调子序列长度

        dp[0] = 1;

        for (int x = 1; x < n; x++) {
            dp[x] = 1;
            for (int y = 0; y < x; y++) {
                if (a[y] > a[x]) continue;
                dp[x] = Math.max(dp[x], dp[y] + 1);
            }

        }
        int max = dp[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(dp[i], max);
        }
        System.out.println(max);

    }
}
